#include<stdio.h>
#include<iostream>
using namespace std;

//查找表 是由同一类型的数据元素(或记录) 构成的集合。 由于"集合"中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构 
//关键字：主关键字，次关键字
//查找表的分类:  静态查找表,  动态查找表 
//查找算法的评价指标：
//		关键字的平均比较次数，也称平均查找长度 ASL (Average Search Length) 



//线性表的查找(3种) 

//1.顺序查找(线性查找)
//	 应用范围：顺序表或线性链表表示的静态查找表; 表内元素之间无序 
//		顺序表的表示：
//		数据元素类型的定义： 
typedef int KeyType;
typedef struct{
	KeyType key; //关键字域
  /*...*/        //其他域 
}ElemType;

typedef struct {  //顺序表结构类型定义 
	ElemType *R;  //表基址 
	int length;   //表长 
}SSTable; //Sequential Search Table
SSTable ST; //定义顺序表ST 

//算法7.1 在顺序表ST中查找值为key的数据元素 
int Search_Seq(SSTable ST, KeyType key){
	//若成功返回其位置信息, 否则返回0
	for(int i = ST.length; i >= 1; --i) {
		if(ST.R[i].key == key) return i;
	}
	return 0;	
}
//改进：把待查关键字key存入表头("哨兵", "监视哨"), 从后面开始逐个比较，可免去查找过程中每一步都要检测是否查找完毕，加快速度。 
int Search_Sq(SSTable ST, KeyType key){
	ST.R[0].key = key;
	int i;
	for(int i = ST.length; ST.R[i].key != key; --i);
	return i;
} 


//2.算法7.3 折半查找(二分或对分查找)：每次将待查记录所在区间缩小一半 
int Search_Bin(SSTable ST, KeyType key){
	int high = ST.length;
	int low = 1;  //置区间初值 
	int mid;
	while(low <= high){
	    mid = (high + low) / 2;
		if(ST.R[mid].key == key) return mid; //找到待查元素 
		else if(key < ST.R[mid].key) //缩小查找区间 
			high = mid - 1;   //继续在前半区间进行查找 
		else low = mid + 1;   //继续在后半区间进行查找 
	} 
	return 0; //顺序表中不存在待查元素 
}
//折半查找的递归算法如下：
int Search_Bi(SSTable ST, KeyType key, int low, int high){
	if(low > high) return 0; //查找不到时返回0
	int mid = (low + high) / 2;
	if(key == ST.R[mid].key) return mid;
	else if(key < ST.R[mid].key) {
		Search_Bi(ST, key, low, mid - 1);
	} else {
		Search_Bi(ST, key, mid + 1, high);
	}
}
//判定树   比较次数：┕log2n┙ + 1 


//3.分块查找 (索引顺序表的查找) 
//条件：(1).将表分成几块, 且表或者有序, 或者分块有序 
//		(2).建立"索引表"(每个结点含有最大关键字域和指向本块第一个结点的指针, 且按关键字有序)
//       
int main(void){
	int a = 11;
	int b = a / 2;
	cout<<b;
	return 0;
	
}